package com.leetcode.题库;

import com.leetcode.common.model.ListNode;

/**
 * @author 覃国强
 * @date 2022-03-23 19:46
 */
public class 题库_0328_奇偶链表 {


  static
  class Solution {
    public ListNode oddEvenList(ListNode head) {
      if (head == null || head.next == null) {
        return head;
      }

      ListNode oddHead = head;
      ListNode oddTail = head;

      ListNode evenHead = head.next;
      ListNode evenTail = head.next;

      ListNode node = head.next.next;

      while (node != null) {
        oddTail.next = node;
        oddTail = node;
        node = node.next;

        if (node != null) {
          evenTail.next = node;
          evenTail = node;
          node = node.next;
        }
      }

      oddTail.next = evenHead;
      evenTail.next = null;

      return oddHead;
    }
  }

}
